package org.hot100.h079;

/**
 * @Author: wjy
 * @Date: 2021/12/28 10:05
 */
public class Solution {

    public static void main(String[] args) {
        char[][] board = {{'A','B','C','E'},{'S','F','C','S'},{'A','C','E','E'}};
        //char[][] board = {{'a', 'b'}};
        //char[][] board = {{'C', 'A', 'A'}, {'A', 'A', 'A'}, {'B', 'C', 'D'}};
        String word = "ABCCEC";
        //String word = "ba";
        //String word = "AAB";

        Solution solution = new Solution();
        System.out.println(solution.exist(board, word));
    }

    public boolean exist(char[][] board, String word) {
        if (board.length == 0) {
            return false;
        }

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (this.recursive(board, word, 0, i, j)) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean recursive(char[][] board, String word, int charIndex, int m, int n) {
        if (m >= board.length || m < 0 || n >= board[0].length || n < 0 || charIndex >= word.length() || word.charAt(charIndex) == 0) {
            return false;
        }
        if (board[m][n] == word.charAt(charIndex)) {
            charIndex++;
            board[m][n] = 0;
            if (this.recursive(board, word, charIndex, m + 1, n)) {
                return true;
            }
            if (this.recursive(board, word, charIndex, m - 1, n)) {
                return true;
            }
            if (this.recursive(board, word, charIndex, m, n - 1)) {
                return true;
            }
            if (this.recursive(board, word, charIndex, m, n + 1)) {
                return true;
            }

            // 将前面变为0的字符，复原
            board[m][n] = word.charAt(charIndex - 1);

            if (charIndex == word.length()) {
                return true;
            }

        }

        return false;
    }

}
